#pragma once
#include "Runtime/BattleFirePrefix.h"
#include "ThreadSafeCounter.h"

namespace Alice{
    #define checkLockFreePointerList
    FORCEINLINE void TestCriticalStall()
    {
    }
    void LockFreeTagCounterHasOverflowed();
    void LockFreeLinksExhausted(uint32 TotalNum);
    void* LockFreeAllocLinks(SIZE_T AllocSize);
    void LockFreeFreeLinks(SIZE_T AllocSize, void* Ptr);

    #define MAX_LOCK_FREE_LINKS_AS_BITS (26)
    #define MAX_LOCK_FREE_LINKS (1 << 26)

    template<class T, unsigned int MaxTotalItems, unsigned int ItemsPerPage>
    class TLockFreeAllocOnceIndexedAllocator
    {
        enum
        {
            MaxBlocks = (MaxTotalItems + ItemsPerPage - 1) / ItemsPerPage
        };
    public:

        TLockFreeAllocOnceIndexedAllocator()
        {
            NextIndex.Increment(); // skip the null ptr
            for (uint32 Index = 0; Index < MaxBlocks; Index++)
            {
                Pages[Index] = nullptr;
            }
        }

        FORCEINLINE uint32 Alloc(uint32 Count = 1)
        {
            uint32 FirstItem = NextIndex.Add(Count);
            if (FirstItem + Count > MaxTotalItems)
            {
                LockFreeLinksExhausted(MaxTotalItems);
            }
            for (uint32 CurrentItem = FirstItem; CurrentItem < FirstItem + Count; CurrentItem++)
            {
                new (GetRawItem(CurrentItem)) T();
            }
            return FirstItem;
        }
        FORCEINLINE T* GetItem(uint32 Index)
        {
            if (!Index)
            {
                return nullptr;
            }
            uint32 BlockIndex = Index / ItemsPerPage;
            uint32 SubIndex = Index % ItemsPerPage;
            checkLockFreePointerList(Index < (uint32)NextIndex.GetValue() && Index < MaxTotalItems&& BlockIndex < MaxBlocks&& Pages[BlockIndex]);
            return Pages[BlockIndex] + SubIndex;
        }

    private:
        void* GetRawItem(uint32 Index)
        {
            uint32 BlockIndex = Index / ItemsPerPage;
            uint32 SubIndex = Index % ItemsPerPage;
            checkLockFreePointerList(Index && Index < (uint32)NextIndex.GetValue() && Index < MaxTotalItems&& BlockIndex < MaxBlocks);
            if (!Pages[BlockIndex])
            {
                T* NewBlock = (T*)LockFreeAllocLinks(ItemsPerPage * sizeof(T));
                T* ExpectedNullPtr=nullptr;
                if (!Pages[BlockIndex].compare_exchange_strong(ExpectedNullPtr,NewBlock))
                {
                    // we lost discard block
                    checkLockFreePointerList(Pages[BlockIndex] && Pages[BlockIndex] != NewBlock);
                    LockFreeFreeLinks(ItemsPerPage * sizeof(T), NewBlock);
                }
                else
                {
                    checkLockFreePointerList(Pages[BlockIndex]);
                }
            }
            return (void*)(Pages[BlockIndex] + SubIndex);
        }
        ThreadSafeCounter NextIndex;
        std::atomic<T*> Pages[MaxBlocks];
    };


    #define MAX_TagBitsValue (uint64(1) << (64 - MAX_LOCK_FREE_LINKS_AS_BITS))

    MS_ALIGN(8)
    struct LockFreeLinkNode//CounterAndState(Other 40 Bits) Ptr(MAX_LOCK_FREE_LINKS_AS_BITS 26 Bits)
    {
        static FORCEINLINE uint64 GetCounterAndState(uint64 node)
        {
            return (node >> MAX_LOCK_FREE_LINKS_AS_BITS);
        }
        static FORCEINLINE uint32 GetLinkPtr(uint64 node)
        {
            return uint32(node & (MAX_LOCK_FREE_LINKS - 1));
        }
        static FORCEINLINE uint64 MakeNode(uint32 LinkPtr, uint64 CounterAndState) {
            return (uint64(LinkPtr) | (CounterAndState << MAX_LOCK_FREE_LINKS_AS_BITS));
        }
        template<uint64 ABAInc>
        static FORCEINLINE uint64 GetState(uint64 node)
        {
            return (node >> MAX_LOCK_FREE_LINKS_AS_BITS) & (ABAInc - 1);
        }
        
        template<uint64 TABAInc>
        static FORCEINLINE uint64 SetState(uint64 node,uint64 Value)
        {
            const uint32 Ptr=GetLinkPtr(node);
            const uint64 CounterAndState=(GetCounterAndState(node) & ~(TABAInc - 1)) | Value;
            return MakeNode(Ptr,CounterAndState);
        }
        template<uint64 ABAInc>
        static FORCEINLINE uint64 AdvanceCounterAndState(uint64 LinkNode) {
            const uint64 LinkNodeCounterAndState = GetCounterAndState(LinkNode);
            const uint64 AdvancedLinkNodeCounterAndState = LinkNodeCounterAndState + ABAInc;
            const uint64 AdvancedLinkNode = MakeNode(GetLinkPtr(LinkNode),AdvancedLinkNodeCounterAndState);
            if(AdvancedLinkNodeCounterAndState<LinkNodeCounterAndState)
            {
                LockFreeTagCounterHasOverflowed();
            }
            return AdvancedLinkNode;
        }
        template<uint64 ABAInc>
        static FORCEINLINE uint64 MakeNodeWithLinkPtrAndAdvanceOldCounterAndState(uint64 OldLinkNode,uint32 LinkPtr) {
            const uint64 LinkNodeCounterAndState = GetCounterAndState(OldLinkNode);
            const uint64 AdvancedLinkNodeCounterAndState = LinkNodeCounterAndState + ABAInc;
            const uint64 AdvancedLinkNode = MakeNode(LinkPtr,AdvancedLinkNodeCounterAndState);
            if(AdvancedLinkNodeCounterAndState<LinkNodeCounterAndState)
            {
                LockFreeTagCounterHasOverflowed();
            }
            return AdvancedLinkNode;
        }
        void Init()
        {
            mAtomicProxy=0;
        }
        std::atomic<uint64> mAtomicProxy;
    } GCC_ALIGN(8);

    struct FIndexedLockFreeLink
    {
        LockFreeLinkNode DoubleNext;
        void* Payload;
        uint32 SingleNext;
    };

    // there is a version of this code that uses 128 bit atomics to avoid the indirection, that is why we have this policy class at all.
    struct FLockFreeLinkPolicy
    {
        enum
        {
            MAX_BITS_IN_TLinkPtr = MAX_LOCK_FREE_LINKS_AS_BITS
        };
        typedef LockFreeLinkNode TDoublePtr;
        typedef FIndexedLockFreeLink TLink;
        typedef uint32 TLinkPtr;
        typedef TLockFreeAllocOnceIndexedAllocator<FIndexedLockFreeLink, MAX_LOCK_FREE_LINKS, 16384> TAllocator;

        static FORCEINLINE FIndexedLockFreeLink* DerefLink(uint32 Ptr)
        {
            return LinkAllocator.GetItem(Ptr);
        }
        static FORCEINLINE FIndexedLockFreeLink* IndexToLink(uint32 Index)
        {
            return LinkAllocator.GetItem(Index);
        }
        static FORCEINLINE uint32 IndexToPtr(uint32 Index)
        {
            return Index;
        }
        static uint32 AllocLockFreeLink();
        static void FreeLockFreeLink(uint32 Item);
        static TAllocator LinkAllocator;
    };

    template<int TPaddingForCacheContention, uint64 TABAInc = 1>
    class FLockFreePointerListLIFORoot : public Noncopyable
    {
        typedef FLockFreeLinkPolicy::TDoublePtr TDoublePtr;
        typedef FLockFreeLinkPolicy::TLink TLink;
        typedef FLockFreeLinkPolicy::TLinkPtr TLinkPtr;

    public:
        FORCEINLINE FLockFreePointerListLIFORoot()
        {
            // We want to make sure we have quite a lot of extra counter values to avoid the ABA problem. This could probably be relaxed, but eventually it will be dangerous. 
            // The question is "how many queue operations can a thread starve for".
            static_assert(MAX_TagBitsValue / TABAInc >= (1 << 23), "risk of ABA problem");
            static_assert((TABAInc & (TABAInc - 1)) == 0, "must be power of two");
            Reset();
        }

        void Reset()
        {
            Head.Init();
        }

        void Push(TLinkPtr Item)
        {
            while (true)
            {
                uint64 CurrentHeadNode = Head.mAtomicProxy.load();
                const uint64 NewHeadNode = LockFreeLinkNode::MakeNodeWithLinkPtrAndAdvanceOldCounterAndState<TABAInc>(CurrentHeadNode,Item);
                FLockFreeLinkPolicy::DerefLink(Item)->SingleNext = LockFreeLinkNode::GetLinkPtr(CurrentHeadNode);
                if (Head.mAtomicProxy.compare_exchange_weak(CurrentHeadNode, NewHeadNode))
                {
                    break;
                }
            }
        }
        bool PushIf(void* InPayload, bool(*OkToPush)(uint64),TLinkPtr ItemToPush)
        {
            while (true)
            {
                uint64 CurrentHeadNode = Head.mAtomicProxy.load();
                const uint32 CurrentNode= LockFreeLinkNode::GetLinkPtr(CurrentHeadNode);
                const uint64 LocalState = LockFreeLinkNode::GetState<TABAInc>(CurrentHeadNode);
                TLinkPtr Item = 0;
                if (OkToPush(LocalState))
                {
                    if (!ItemToPush)
                    {
                        ItemToPush = FLockFreeLinkPolicy::AllocLockFreeLink();
                        FLockFreeLinkPolicy::DerefLink(ItemToPush)->Payload = InPayload;
                    }
                    Item=ItemToPush;
                }
                if (!Item)
                {
                    return false;
                }
                const uint64 NewHeadNode = LockFreeLinkNode::MakeNode(Item,LockFreeLinkNode::GetCounterAndState(CurrentHeadNode)+TABAInc);
                FLockFreeLinkPolicy::DerefLink(Item)->SingleNext = CurrentNode;
                if (Head.mAtomicProxy.compare_exchange_weak(CurrentHeadNode, NewHeadNode))
                {
                    break;
                }
            }
            return true;
        }
        TLinkPtr Pop()
        {
            TLinkPtr Item = 0;
            while (true)
            {
                AliceUInt64 threadLocalHead=Head.mAtomicProxy.load();
                Item = LockFreeLinkNode::GetLinkPtr(threadLocalHead);
                if (!Item)
                {
                    break;
                }
                AliceUInt64 threadLocalNewHead = LockFreeLinkNode::AdvanceCounterAndState<TABAInc>(threadLocalHead);
                TLink* ItemP = FLockFreeLinkPolicy::DerefLink(Item);
                threadLocalNewHead = LockFreeLinkNode::MakeNode(ItemP->SingleNext,  LockFreeLinkNode::GetCounterAndState(threadLocalNewHead));

                if (Head.mAtomicProxy.compare_exchange_weak(threadLocalHead, threadLocalNewHead))
                {
                    ItemP->SingleNext = 0;
                    break;
                }
            }
            return Item;
        }

        TLinkPtr PopAll()
        {
            TLinkPtr Item = 0;
            while (true)
            {
                AliceUInt64 threadLocalHead = Head.mAtomicProxy.load();
                Item = LockFreeLinkNode::GetLinkPtr(threadLocalHead);
                if (!Item)
                {
                    break;
                }
                AliceUInt64 threadNewHead = LockFreeLinkNode::AdvanceCounterAndState<TABAInc>(threadLocalHead);
                threadNewHead = LockFreeLinkNode::MakeNode(0, LockFreeLinkNode::GetCounterAndState(threadNewHead));
                if (Head.mAtomicProxy.compare_exchange_weak(threadLocalHead,threadNewHead))
                {
                    break;
                }
            }
            return Item;
        }

        TLinkPtr PopAllAndChangeState(uint64(*StateChange)(uint64))
        {
            TLinkPtr Item = 0;
            while (true)
            {
                uint64 LocalHead=Head.mAtomicProxy.load();
                Item = LockFreeLinkNode::GetLinkPtr(LocalHead);
                uint64 NewHead=LockFreeLinkNode::AdvanceCounterAndState<TABAInc>(LocalHead);
                uint64 NewHeadState=StateChange(LockFreeLinkNode::GetState<TABAInc>(LocalHead));
                NewHead=LockFreeLinkNode::SetState<TABAInc>(NewHead,NewHeadState);
                NewHead=LockFreeLinkNode::MakeNode(0,LockFreeLinkNode::GetCounterAndState(NewHead));
                
                if (Head.mAtomicProxy.compare_exchange_weak(LocalHead, NewHead))
                {
                    break;
                }
            }
            return Item;
        }

        FORCEINLINE bool IsEmpty() const
        {
            return !LockFreeLinkNode::GetLinkPtr(Head.mAtomicProxy.load());
        }

        FORCEINLINE uint64 GetState() const
        {
            const AliceUInt64 threadLocalHead = Head.mAtomicProxy.load();
            return LockFreeLinkNode::GetState<TABAInc>(threadLocalHead);
        }

    private:
        TDoublePtr Head;
    };

    template<class T, int TPaddingForCacheContention, uint64 TABAInc = 1>
    class FLockFreePointerListLIFOBase : public Noncopyable
    {
        typedef FLockFreeLinkPolicy::TDoublePtr TDoublePtr;
        typedef FLockFreeLinkPolicy::TLink TLink;
        typedef FLockFreeLinkPolicy::TLinkPtr TLinkPtr;
    public:
        void Reset()
        {
            RootList.Reset();
        }

        void Push(T* InPayload)
        {
            TLinkPtr Item = FLockFreeLinkPolicy::AllocLockFreeLink();
            FLockFreeLinkPolicy::DerefLink(Item)->Payload = InPayload;
            RootList.Push(Item);
        }

        bool PushIf(T* InPayload, bool(*OkToPush)(uint64))
        {
            TLinkPtr Item = 0;
            if (!RootList.PushIf(InPayload,OkToPush,Item))
            {
                if (Item)
                {
                    FLockFreeLinkPolicy::FreeLockFreeLink(Item);
                }
                return false;
            }
            return true;
        }


        T* Pop()
        {
            TLinkPtr Item = RootList.Pop();
            T* Result = nullptr;
            if (Item)
            {
                Result = (T*)FLockFreeLinkPolicy::DerefLink(Item)->Payload;
                FLockFreeLinkPolicy::FreeLockFreeLink(Item);
            }
            return Result;
        }

        void PopAll(std::vector<T*>&OutArray)
        {
            TLinkPtr Links = RootList.PopAll();
            while (Links)
            {
                TLink* LinksP = FLockFreeLinkPolicy::DerefLink(Links);
                OutArray.push_back((T*)LinksP->Payload);
                TLinkPtr Del = Links;
                Links = LinksP->SingleNext;
                FLockFreeLinkPolicy::FreeLockFreeLink(Del);
            }
        }

        void PopAllAndChangeState(std::vector<T*>& OutArray, uint64(*StateChange)(uint64))
        {
            TLinkPtr Links = RootList.PopAllAndChangeState(StateChange);
            while (Links)
            {
                TLink* LinksP = FLockFreeLinkPolicy::DerefLink(Links);
                OutArray.push_back((T*)LinksP->Payload);
                TLinkPtr Del = Links;
                Links = LinksP->SingleNext;
                FLockFreeLinkPolicy::FreeLockFreeLink(Del);
            }
        }

        FORCEINLINE bool IsEmpty() const
        {
            return RootList.IsEmpty();
        }

        FORCEINLINE uint64 GetState() const
        {
            return RootList.GetState();
        }

    private:

        FLockFreePointerListLIFORoot<TPaddingForCacheContention, TABAInc> RootList;
    };

    template<class T, int TPaddingForCacheContention, uint64 TABAInc = 1>
    class FLockFreePointerFIFOBase : public Noncopyable
    {
        typedef FLockFreeLinkPolicy::TDoublePtr TDoublePtr;
        typedef FLockFreeLinkPolicy::TLink TLink;
        typedef FLockFreeLinkPolicy::TLinkPtr TLinkPtr;
    public:

        FORCEINLINE FLockFreePointerFIFOBase()
        {
            // We want to make sure we have quite a lot of extra counter values to avoid the ABA problem. This could probably be relaxed, but eventually it will be dangerous. 
            // The question is "how many queue operations can a thread starve for".
            static_assert(TABAInc <= 65536, "risk of ABA problem");
            static_assert((TABAInc & (TABAInc - 1)) == 0, "must be power of two");
            
            const TLinkPtr Stub = FLockFreeLinkPolicy::AllocLockFreeLink();
            Head.mAtomicProxy=LockFreeLinkNode::MakeNode(Stub,0);
            Tail.mAtomicProxy=LockFreeLinkNode::MakeNode(Stub,0);
        }

        void Push(T* InPayload)
        {
            TLinkPtr Item = FLockFreeLinkPolicy::AllocLockFreeLink();
            FLockFreeLinkPolicy::DerefLink(Item)->Payload = InPayload;
            uint64 LocalTail;
            while (true)
            {
                LocalTail=Tail.mAtomicProxy.load();
                TLink* LocalTailP = FLockFreeLinkPolicy::DerefLink(LockFreeLinkNode::GetLinkPtr(LocalTail));
                uint64 LocalNext=LocalTailP->DoubleNext.mAtomicProxy.load();
                const uint64 TestLocalTail=Tail.mAtomicProxy.load();
                if (TestLocalTail == LocalTail)
                {
                    if (LockFreeLinkNode::GetLinkPtr(LocalNext))
                    {
                        const uint64 NewTail=LockFreeLinkNode::MakeNodeWithLinkPtrAndAdvanceOldCounterAndState<TABAInc>(LocalTail,LockFreeLinkNode::GetLinkPtr(LocalNext));
                        Tail.mAtomicProxy.compare_exchange_strong(LocalTail,NewTail);
                    }
                    else
                    {
                        const uint64 NewNext=LockFreeLinkNode::MakeNodeWithLinkPtrAndAdvanceOldCounterAndState<TABAInc>(LocalNext,Item);
                        if (LocalTailP->DoubleNext.mAtomicProxy.compare_exchange_weak(LocalNext,NewNext))
                        {
                            break;
                        }
                    }
                }
            }
            {
                const uint64 NewTail=LockFreeLinkNode::MakeNodeWithLinkPtrAndAdvanceOldCounterAndState<TABAInc>(LocalTail,Item);
                Tail.mAtomicProxy.compare_exchange_strong(LocalTail,NewTail);
            }
        }

        T* Pop()
        {
            T* Result = nullptr;
            uint64 LocalHead;
            while (true)
            {
                LocalHead=Head.mAtomicProxy.load();
                uint64 LocalTail=Tail.mAtomicProxy.load();
                uint64 LocalNext=FLockFreeLinkPolicy::DerefLink( LockFreeLinkNode::GetLinkPtr(LocalHead))->DoubleNext.mAtomicProxy.load();
                const uint64 LocalHeadTest=Head.mAtomicProxy.load();
                if (LocalHead == LocalHeadTest)
                {
                    if (LockFreeLinkNode::GetLinkPtr(LocalHead) == LockFreeLinkNode::GetLinkPtr(LocalTail))
                    {
                        if (!LockFreeLinkNode::GetLinkPtr(LocalNext))
                        {
                            return nullptr;
                        }
                        const uint64 NewTail=LockFreeLinkNode::MakeNodeWithLinkPtrAndAdvanceOldCounterAndState<TABAInc>(LocalTail,LockFreeLinkNode::GetLinkPtr(LocalNext));
                        Tail.mAtomicProxy.compare_exchange_strong(LocalTail,NewTail);
                    }
                    else
                    {
                        Result = (T*)FLockFreeLinkPolicy::DerefLink(LockFreeLinkNode::GetLinkPtr(LocalNext))->Payload;
                        uint64 NewHead=LockFreeLinkNode::MakeNodeWithLinkPtrAndAdvanceOldCounterAndState<TABAInc>(LocalHead,LockFreeLinkNode::GetLinkPtr(LocalNext));
                        if (Head.mAtomicProxy.compare_exchange_weak(LocalHead, NewHead))
                        {
                            break;
                        }
                    }
                }
            }
            FLockFreeLinkPolicy::FreeLockFreeLink( LockFreeLinkNode::GetLinkPtr(LocalHead));
            return Result;
        }

        FORCEINLINE bool IsEmpty() const
        {
            AliceUInt64 currentHeadNode = Head.mAtomicProxy.load();
            AliceUInt32 currentItem = GetItemPtr(currentHeadNode);
            AliceUInt64 nextNode = FLockFreeLinkPolicy::DerefLink(currentItem)->DoubleNext;
            return !GetItemPtr(nextNode);
        }

    private:
        TDoublePtr Head;
        TDoublePtr Tail;
    };


    template<class T, int TPaddingForCacheContention, int NumPriorities>
    class FStallingTaskQueue : public Noncopyable
    {
        typedef FLockFreeLinkPolicy::TDoublePtr TDoublePtr;
        typedef FLockFreeLinkPolicy::TLink TLink;
        typedef FLockFreeLinkPolicy::TLinkPtr TLinkPtr;
    public:
        FStallingTaskQueue()
        {
            MasterState.Init();
        }
        int32 Push(T* InPayload, uint32 Priority)
        {
            AliceUInt64 currentMasterState = MasterState.mAtomicProxy.load();
            AliceUInt32 currentMasterPtr = LockFreeLinkNode::GetLinkPtr(currentMasterState);
            PriorityQueues[Priority].Push(InPayload);

            AliceUInt64 newMaterState = LockFreeLinkNode::AdvanceCounterAndState<1>(currentMasterState);
            int32 ThreadToWake = FindThreadToWake(currentMasterPtr);

            if (ThreadToWake >= 0)
            {
                newMaterState = LockFreeLinkNode::MakeNode(TurnOffBit(currentMasterPtr, ThreadToWake), LockFreeLinkNode::GetCounterAndState(newMaterState));
            }
            else
            {
                newMaterState = LockFreeLinkNode::MakeNode(currentMasterPtr, LockFreeLinkNode::GetCounterAndState(newMaterState));
            }
            while (!MasterState.mAtomicProxy.compare_exchange_weak(currentMasterState, newMaterState))
            {
                currentMasterState = MasterState.mAtomicProxy.load();
                currentMasterPtr = LockFreeLinkNode::GetLinkPtr(currentMasterState);
                newMaterState = LockFreeLinkNode::AdvanceCounterAndState<1>(currentMasterState);
                ThreadToWake = FindThreadToWake(currentMasterPtr);
                if (ThreadToWake >= 0)
                {
                    newMaterState = LockFreeLinkNode::MakeNode(TurnOffBit(currentMasterPtr, ThreadToWake), LockFreeLinkNode::GetCounterAndState(newMaterState));
                }
                else
                {
                    newMaterState = LockFreeLinkNode::MakeNode(currentMasterPtr, LockFreeLinkNode::GetCounterAndState(newMaterState));
                }
            }
            return ThreadToWake;
        }

        T* Pop(int32 MyThread, bool bAllowStall)
        {
            while (true)
            {
                AliceUInt64 currentMasterState = MasterState.mAtomicProxy.load();
                for (int32 Index = 0; Index < NumPriorities; Index++)
                {
                    T * Result = PriorityQueues[Index].Pop();
                    if (Result)
                    {
                        while (true)
                        {
                            const AliceUInt64 newMasterState = LockFreeLinkNode::AdvanceCounterAndState<1>(currentMasterState);
                            if (MasterState.mAtomicProxy.compare_exchange_weak(currentMasterState,newMasterState))
                            {
                                return Result;
                            }
                            currentMasterState = MasterState.mAtomicProxy.load();
                        }
                    }
                }
                if (!bAllowStall)
                {
                    break; // if we aren't stalling, we are done, the queues are empty
                }
                {
                    AliceUInt64 newMasterState = LockFreeLinkNode::AdvanceCounterAndState<1>(currentMasterState);
                    newMasterState = LockFreeLinkNode::MakeNode(TurnOnBit( LockFreeLinkNode::GetLinkPtr(currentMasterState), MyThread), LockFreeLinkNode::GetCounterAndState(newMasterState));
                    if (MasterState.mAtomicProxy.compare_exchange_weak(currentMasterState,newMasterState))
                    {
                        break;
                    }
                }
            }
            return nullptr;
        }

    private:

        static int32 FindThreadToWake(TLinkPtr Ptr)
        {
            int32 Result = -1;
            UPTRINT Test = UPTRINT(Ptr);
            if (Test)
            {
                Result = 0;
                while (!(Test & 1))
                {
                    Test >>= 1;
                    Result++;
                }
            }
            return Result;
        }

        static TLinkPtr TurnOffBit(TLinkPtr Ptr, int32 BitToTurnOff)
        {
            return (TLinkPtr)(UPTRINT(Ptr) & ~(UPTRINT(1) << BitToTurnOff));
        }

        static TLinkPtr TurnOnBit(TLinkPtr Ptr, int32 BitToTurnOn)
        {
            return (TLinkPtr)(UPTRINT(Ptr) | (UPTRINT(1) << BitToTurnOn));
        }

        static bool TestBit(TLinkPtr Ptr, int32 BitToTest)
        {
            return !!(UPTRINT(Ptr) & (UPTRINT(1) << BitToTest));
        }

        FLockFreePointerFIFOBase<T, TPaddingForCacheContention> PriorityQueues[NumPriorities];
        // not a pointer to anything, rather tracks the stall state of all threads servicing this queue.
        TDoublePtr MasterState;
    };




    template<class T, int TPaddingForCacheContention>
    class TLockFreePointerListLIFOPad : private FLockFreePointerListLIFOBase<T, TPaddingForCacheContention>
    {
    public:

        /**
        *	Push an item onto the head of the list.
        *
        *	@param NewItem, the new item to push on the list, cannot be NULL.
        */
        void Push(T* NewItem)
        {
            FLockFreePointerListLIFOBase<T, TPaddingForCacheContention>::Push(NewItem);
        }

        /**
        *	Pop an item from the list or return NULL if the list is empty.
        *	@return The popped item, if any.
        */
        T* Pop()
        {
            return FLockFreePointerListLIFOBase<T, TPaddingForCacheContention>::Pop();
        }

        /**
        *	Pop all items from the list.
        *
        *	@param Output The array to hold the returned items. Must be empty.
        */
        void PopAll(std::vector<T*>& Output)
        {
            FLockFreePointerListLIFOBase<T, TPaddingForCacheContention>::PopAll(Output);
        }

        /**
        *	Check if the list is empty.
        *
        *	@return true if the list is empty.
        *	CAUTION: This methods safety depends on external assumptions. For example, if another thread could add to the list at any time, the return value is no better than a best guess.
        *	As typically used, the list is not being access concurrently when this is called.
        */
        FORCEINLINE bool IsEmpty() const
        {
            return FLockFreePointerListLIFOBase<T, TPaddingForCacheContention>::IsEmpty();
        }
    };

    template<class T>
    class TLockFreePointerListLIFO : public TLockFreePointerListLIFOPad<T, 0>
    {

    };

    template<class T, int TPaddingForCacheContention>
    class TLockFreePointerListUnordered : public TLockFreePointerListLIFOPad<T, TPaddingForCacheContention>
    {

    };

    template<class T, int TPaddingForCacheContention>
    class TLockFreePointerListFIFO : private FLockFreePointerFIFOBase<T, TPaddingForCacheContention>
    {
    public:

        /**
        *	Push an item onto the head of the list.
        *
        *	@param NewItem, the new item to push on the list, cannot be NULL.
        */
        void Push(T* NewItem)
        {
            FLockFreePointerFIFOBase<T, TPaddingForCacheContention>::Push(NewItem);
        }

        /**
        *	Pop an item from the list or return NULL if the list is empty.
        *	@return The popped item, if any.
        */
        T* Pop()
        {
            return FLockFreePointerFIFOBase<T, TPaddingForCacheContention>::Pop();
        }

        /**
        *	Pop all items from the list.
        *
        *	@param Output The array to hold the returned items. Must be empty.
        */
        void PopAll(std::vector<T*>& Output)
        {
            FLockFreePointerFIFOBase<T, TPaddingForCacheContention>::PopAll(Output);
        }

        /**
        *	Check if the list is empty.
        *
        *	@return true if the list is empty.
        *	CAUTION: This methods safety depends on external assumptions. For example, if another thread could add to the list at any time, the return value is no better than a best guess.
        *	As typically used, the list is not being access concurrently when this is called.
        */
        FORCEINLINE bool IsEmpty() const
        {
            return FLockFreePointerFIFOBase<T, TPaddingForCacheContention>::IsEmpty();
        }
    };


    template<class T, int TPaddingForCacheContention>
    class TClosableLockFreePointerListUnorderedSingleConsumer : private FLockFreePointerListLIFOBase<T, TPaddingForCacheContention, 2>
    {
    public:

        /**
        *	Reset the list to the initial state. Not thread safe, but used for recycling when we know all users are gone.
        */
        void Reset()
        {
            FLockFreePointerListLIFOBase<T, TPaddingForCacheContention, 2>::Reset();
        }

        /**
        *	Push an item onto the head of the list, unless the list is closed
        *
        *	@param NewItem, the new item to push on the list, cannot be NULL
        *	@return true if the item was pushed on the list, false if the list was closed.
        */
        bool PushIfNotClosed(T* NewItem)
        {
            return FLockFreePointerListLIFOBase<T, TPaddingForCacheContention, 2>::PushIf(NewItem, [](uint64 State)->bool {return !(State & 1); });
        }

        /**
        *	Pop all items from the list and atomically close it.
        *
        *	@param Output The array to hold the returned items. Must be empty.
        */
        void PopAllAndClose(std::vector<T*>& Output)
        {
            auto CheckOpenAndClose = [](uint64 State) -> uint64
            {
                return State | 1;
            };
            FLockFreePointerListLIFOBase<T, TPaddingForCacheContention, 2>::PopAllAndChangeState(Output, CheckOpenAndClose);
        }

        /**
        *	Check if the list is closed
        *
        *	@return true if the list is closed.
        */
        bool IsClosed() const
        {
            return !!(FLockFreePointerListLIFOBase<T, TPaddingForCacheContention, 2>::GetState() & 1);
        }

    };
}